A Fourier transform may be used to determine a spectrum (frequency content) of an input waveform. A discrete Fourier transform (DFT) may be applied to a sampled version of the input waveform. Fast Fourier Transform (FFT) corresponds to techniques for determining DFTs of the sampled input waveform that typically require fewer complex multiplications and/or additions than naïve O(N2) computations of the DFT.
Determining the FFT includes complex multiplications by complex roots of unity called twiddle factors, with the number of the twiddle factors depending on a number of samples of the input waveform. If the number of samples is relatively large, the number of the twiddle factors and the number of points in the output spectrum are also relatively large. The samples of the input waveform, the twiddle factors and the output spectrum may be stored in the system memory. Thus, the memory footprint (amount of memory used) depends on the number of samples and the number of twiddle factors. For example, the memory footprint may correspond to three times the number of samples in order to accommodate the samples of input waveform, the twiddle factors and the output spectrum. This memory footprint may exceed the capacity of the system memory in some situations. It may therefore be desirable to reduce this memory footprint.
Although the following Detailed Description will proceed with reference being made to illustrative embodiments, many alternatives, modifications, and variations thereof will be apparent to those skilled in the art.